
//存在重复元素III
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>&  nums, int indexDiff, int valueDiff) {
        //使用 滑动窗口+二分

        //控制一段长度小于indexDiff的区间，以nums[i]为基点看理他最近的数是否满足第二个条件
        int left = 0, n = nums.size();
        set<int> s;
        for (int right = 0; right < n; right++)
        {
            auto l = s.lower_bound((long)nums[right]-valueDiff);

            if ((l != s.end() && abs(*l - (long)nums[right]) <= valueDiff))
                return true;

            if (right - left == indexDiff)
                s.erase(nums[left++]);
                
            s.insert(nums[right]);
        }
        return false;
    }
};
